/*
 * @lc app=leetcode.cn id=1723 lang=cpp
 *
 * [1723] 完成所有工作的最短时间
 */

// @lc code=start
class Solution
{
public:
    void backtrack(vector<int> &jobs, int idx, vector<int> &slot, int maxNum, int &ans)
    {
        if (idx == jobs.size())
        {
            ans = maxNum;
            return;
        }

        for (int i = 0; i < slot.size(); i++)
        {
            if (slot[i] + jobs[idx] > ans)
                continue;
            slot[i] += jobs[idx];
            backtrack(jobs, idx + 1, slot, max(maxNum, slot[i]), ans);
            slot[i] -= jobs[idx];
            if (slot[i] == 0)
                break;
        }
    };

    int minimumTimeRequired(vector<int> &jobs, int k)
    {
        vector<int> slot(k, 0);
        int ans = INT_MAX;
        backtrack(jobs, 0, slot, 0, ans);
        return ans;
    };
};
// @lc code=end
